package base;

/**
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/
 *
 * @author mazouri
 * @create 2021-12-27 9:46
 */
public class _2_lengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        if (nums == null|| nums.length == 0) return 0;

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res, L(nums, i));
        }

        return res;
    }

    /**
     * 返回从数组第i个数字开始的最长子序列长度
     * @param nums
     * @param i
     * @return
     */
    private int L(int[] nums, int i) {
        //由于后面没有元素与它构成子序列了，本身 返回1
        if (i == nums.length) return 1;

        int max = 0;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] > nums[i]) max = Math.max(max, L(nums, j) + 1);
        }

        return max;
    }

    public static void main(String[] args) {
        _2_lengthOfLIS o = new _2_lengthOfLIS();
        System.out.println(o.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }
}
